public class AVLTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        int bf;//左子树减减，右子树加加

        public TreeNode(int val) {
            this.val = val;
        }
    }

    TreeNode root;

    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
        }

        //找位置
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            parent = cur;
            if(cur.val > val) {
                cur = cur.left;
            } else if(cur.val < val) {
                cur = cur.right;
            } else {
                //数据已经存在，直接返回
                return;
            }
        }

        //插入结点
        if(parent.val > val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        node.parent = parent;

        //开始调整AVL树
        cur = node;
        while(parent != null) {

            //调整平衡因子
            if(cur == parent.left) {
                parent.bf--;
            } else {
                parent.bf++;
            }

            //检查AVL树是否需要旋转
            if(parent.bf == 0) {
                return;
            }

            if(parent.bf == -1 || parent.bf == 1) {
                //说明AVL 树已经被影响到平衡性，需要继续向上调整
                cur = parent;
                parent = cur.parent;
            } else if(parent.bf == -2) {
                //平衡因子为 -2，进行旋转操作
                if(cur.bf == -1) {
                    //左左型，进行右单旋
                    rotateRight(parent);
                } else {
                    //cur.bf == 1
                    //左右型，进行左右双旋
                    rotateLR(parent);
                }
            } else {
                //平衡因子为 2，进行旋转操作
                if(cur.bf == 1) {
                    //右右型，进行左单旋
                    rotateLeft(parent);
                } else {
                    //cur.bf == -1
                    //右左型，进行右左双旋
                    rotateRL(parent);
                }
            }
        }
    }

    private void rotateRL(TreeNode parent) {
        TreeNode child = parent.right;
        rotateRight(child);
        rotateLeft(parent);
    }

    private void rotateLR(TreeNode parent) {
        TreeNode child = parent.left;
        rotateLeft(child);
        rotateRight(parent);
    }

    private void rotateRight(TreeNode parent) {
        TreeNode grandparent = parent.parent;
        TreeNode cur = parent.right;
        cur.left = parent;
        parent.parent = cur;
        cur.parent = grandparent;
        parent.bf = cur.bf = 0;
    }

    private void rotateLeft(TreeNode parent) {
        TreeNode grandparent = parent.parent;
        TreeNode cur = parent.left;
        cur.right = parent;
        cur.parent = grandparent;
        parent.parent = cur;
        cur.bf = parent.bf = 0;
    }
}
